package com.kehao.leetcode.middle.sort_search;

import org.junit.Test;

public class TwoDimMartixSearchSolution {
    public boolean searchMatrix(int[][] matrix, int target) {
      return searchMatrix(matrix,target,0,0,matrix.length,matrix[0].length);
    }

    private boolean searchMatrix(int[][] matrix, int target,int starti,int startj,int endi,int endj) {
        int i =starti,j=startj;
        if(endi-starti==1){
            for (int k = j; k < endj; k++) {
                if(matrix[starti][k]==target){
                    return true;
                }
            }
            return false;
        }else if(endj-startj==1){
            for (int k = 0; k < endi; k++) {
                if(matrix[k][startj]==target){
                    return true;
                }
            }
            return false;
        }
        while (i<endi-1&&j<endj-1){
            if(matrix[i][j]==target) return true;
            if(matrix[i][j]>target) return false;
            if(matrix[i+1][j+1]<target){
                i++;j++;
                continue;
            }else if(matrix[i+1][j+1]==target){
                return true;
            }else {
                boolean b1 = searchMatrix(matrix, target, i + 1, startj, endi, j + 1);
                boolean b2 = searchMatrix(matrix, target, starti, j + 1, i + 1, endj);
                return b1||b2;
            }
        }

        if(i!=endi-1){
            return searchMatrix(matrix, target, i + 1, startj, endi, j+1);
        }
        if(j!=endj-1){
            return searchMatrix(matrix, target, starti, j+1, i+1, endj);
        }
        return false;
    }

    @Test
    public void test01(){
        int[][] matrix = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        int target = 5;
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test02(){
        int[][] matrix = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        int target = 20;
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test03(){
        int[][] matrix = {{-5}};
        int target = -5;
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test04(){
        int[][] matrix = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
        int target = 15;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("----------------------------");
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test05(){
        int[][] matrix = {{1,3,5,7,9},{2,4,6,8,10},{11,13,15,17,19},{12,14,16,18,20},{21,22,23,24,25}};
        int target = 11;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("----------------------------");
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test06(){
        int[][] matrix = {{1,4},{2,5},};
        int target =6;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("----------------------------");
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test07(){
        int[][] matrix = {
                {4,7,11,12,16,21,23,26},
                {5,12,17,17,18,23,26,31},
                {8,15,21,25,26,29,33,34},
                {13,20,26,26,29,34,39,40},
                {18,21,31,36,41,42,42,44},
                {19,23,31,39,46,49,50,53},
                {23,25,33,40,50,51,55,60},
                {27,28,33,44,51,56,61,65},
                {32,35,39,45,54,56,65,68},
                {33,38,40,49,56,57,66,71}
        };
        int target =51;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("----------------------------");
        System.out.println(searchMatrix(matrix, target));
    }

    @Test
    public void test08(){
        int[][] matrix = {{2,5},{2,8},{7,9},{7,11},{9,11}};
        int target =7;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("----------------------------");
        System.out.println(searchMatrix(matrix, target));
    }
}
